// 将两个升序链表合并为⼀个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
// 示例：
// 输⼊：1->2->4, 1->3->4
// 输出：1->1->2->3->4->4

// js中没有链表结构，所以需要模拟一个类似于链表的数据结构
class ListNode {
  constructor (val, next = null) {
    this.val = val
    this.next = next
  }
}

// 创建链表的头节点，并设置其值为 1
const head = new ListNode(1)

// 创建节点 2，并将其连接到链表中
const node2 = new ListNode(2)
head.next = node2

// 创建节点 4，并将其连接到链表中
const node4 = new ListNode(4)
node2.next = node4

const head2 = new ListNode(1)

// 创建节点 2，并将其连接到链表中
const node22 = new ListNode(3)
head2.next = node22

// 创建节点 4，并将其连接到链表中
const node42 = new ListNode(4)
node22.next = node42

// let a1 = [1, 2, 4]
// let a2 = [1, 3, 4]

const mergeTwoLists = function (l1, l2) {
  // 如果 l1 为空，直接返回 l2
  if (l1 === null) {
    return l2
  }

  // 如果 l2 为空，直接返回 l1
  if (l2 === null) {
    return l1
  }

  // 比较 l1 和 l2 的值，选择较小的节点作为合并后的链表的头节点
  if (l1.val < l2.val) {
    // 递归调用 mergeTwoLists，将 l1 的下一个节点与 l2 合并，将合并结果赋给 l1 的下一个节点
    // 直到其中的一个节点没有next，也就是next的值为null,才算结束
    l1.next = mergeTwoLists(l1.next, l2)
    // 返回 l1 作为合并后的链表的头节点
    return l1
  } else {
    // 递归调用 mergeTwoLists，将 l1 与 l2 的下一个节点合并，将合并结果赋给 l2 的下一个节点
    l2.next = mergeTwoLists(l1, l2.next)
    // 返回 l2 作为合并后的链表的头节点
    return l2
  }
}

const merge = (head1, head2) => {
  let dummy = new ListNode(0)
  let cur = dummy
  // 新链表，新的值小就先接谁
  // 这里有一直进入循环的条件就是这两个链表都还有值
  // 只要都还有值，就可以进行对比
  while (head1 && head2) {
    if (head1.val < head2.val) {
      // 如果header1小于head2，那它就需要排到前面，
      cur.next = head1
      // 然后删除原来的链表节点head1，把head1的下一个节点提上来充当head1，便于下次循环
      head1 = head1.next
    } else {
      // 如果header1大于head2，那head2就需要排到前面，
      cur.next = head2
      // 同时需要删除head2这个节点，然后把head2.next节点提上来，充当head2，便于下次循环
      head2 = head2.next
    }
    // 把循环出的cur.next的值挂载到cur这个节点上，为了后面有值，没有循环完的，可以继续挂在后面
    cur = cur.next
  }
  // 如果后面还有剩余的就把剩余的接上
  cur.next = head1 == null ? head2 : head1
  return dummy.next
}

// console.log(mergeTwoLists(head, head2))
let m = merge(head, head2)

while (m !== null) {
  console.log(m.val)
  m = m.next
}

// 链表的结构展开就类似于js中的这种数据
let demo1 = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 4,
      next: null
    }
  }
}

let demo2 = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}
